export default class MinHeap<T> {
  private data: T[] = [];
  private length: number = 0;

  constructor(arr: T[] = []) {
    if (arr.length) return;
  }

  insert(value: T) {
    this.data.push(value);
    this.length++;

    this.upHead();
  }

  private upHead() {
    let index = this.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor(index / 2 - 1);
      if (this.data[index] >= this.data[parentIndex]) {
        break;
      }

      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  extract(): T | undefined {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.shift();
    }

    const topValue = this.data[0];
    this.data[0] = this.data.pop()!;
    this.length--;

    this.downHead(0);
    return topValue;
  }

  downHead(start: number) {
    let index = start;
    while (2 * index + 1 <= this.length - 1) {
      let leftIndex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      if (rightIndex < this.length && this.data[rightIndex] < this.data[leftIndex]) {
        leftIndex = rightIndex;
      }

      if (this.data[index] <= this.data[leftIndex]) {
        break;
      }

      this.swap(index, leftIndex);
      index = leftIndex;
    }
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size() {
    return this.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {
    this.data = arr;
    this.length = arr.length;

    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; i >= 0; i--) {
      this.downHead(i);
    }
  }

  private swap(i: number, j: number) {
    let temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
}
